package com.atguigu.main.sort;

/**
 * 冒泡排序 时间复杂度 O(n^2) 空间复杂度O(1)
 *
 * @Author 剧情再美终是戏
 * @Date 2019/12/21
 * @return
 * @Version 1.0
 **/
public class BubbleSort {

    public static int[] bubbleSort(int[] array) {

        for (int i = 0; i < array.length - 1; i++) {
            // -i 是因为i每循环一次，就能找到最大或者最小单位的数值，并把它放到最后一位了，所以每次-i,可以提高效率
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
        return array;
    }

    public static int[] bubbleSort2(int[] data) {
        long startTime = System.currentTimeMillis();
        int arrayLength = data.length;

        for (int i = 0; i < arrayLength - 1; i++) {


            boolean flag = false;
            for (int j = 0; j < arrayLength - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = data[j + 1];
                    data[j + 1] = data[j];
                    data[j] = temp;
                    flag = true;
                }
            }
            if (!flag)
                break;
        }
        System.out.printf("冒泡排序算法\t耗时%dms\n", System.currentTimeMillis() - startTime);
        return data;
    }

    public static void main(String[] args) {
        System.out.println("--------------------------ubbbleSort1");
//        int[] array = {1, 3, 5, 2, 4, 9, 8};
        int[] array = {1, 2, 3, 4, 5, 8, 9};
        int[] ints = BubbleSort.bubbleSort(array);
        for (int anInt : ints) {
            System.out.print(anInt + "\t");
        }
        System.out.println();
        System.out.println("--------------------------bubbleSort2");
//        int[] array2 = {1, 3, 5, 2, 4, 9, 8};
        int[] array2 = {1, 2, 3, 4, 5, 8, 9};
        int[] ints2 = BubbleSort.bubbleSort2(array2);
        for (int anInt : ints2) {
            System.out.print(anInt + "\t");
        }
    }
}
